package com.itheima.leetcode.od.b.logicalsimulation;

import java.util.ArrayList;
import java.util.List;

/**
 * (C卷,200分)- 出错的或电路（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 某生产门电路的厂商发现某一批次的或门电路不稳定，具体现象为计算两个二进制数的或操作时，第一个二进制数中某两个比特位会出现交换，交换的比特位置是随机的，但只交换这两个位，其他位不变。
 * <p>
 * 很明显，这个交换可能会影响最终的或结果，也可能不会有影响。
 * <p>
 * 为了评估影响和定位出错的根因，工程师需要研究在各种交换的可能下，最终的或结果发生改变的情况有多少种。
 * <p>
 * 输入描述
 * <p>
 * 第一行有一个正整数N; 其中1≤N≤1000000。
 * <p>
 * 第二行有一个长为N的二进制数，表示与电路的第一个输入数，即会发生比特交换的输入数。
 * <p>
 * 第三行有一个长为N的二进制数，表示与电路的第二个输入数。注意第二个输入数不会发生比特交换。
 * <p>
 * 输出描述
 * <p>
 * 输出只有一个整数，表示会影响或结果的交换方案个数。
 * <p>
 * 用例
 * <p>
 * 输入	3
 * <p>
 * 010
 * <p>
 * 110
 * <p>
 * 输出	1
 * <p>
 * 说明
 * <p>
 * 原本010和110的或结果是110，但第一个输入数可能会发生如下三种交换：
 * <p>
 * 1、交换第1个比特和第2个比特，第一个输入数变为100，计算结果为110，计算结果不变
 * <p>
 * 2、交换第1个比特和第3个比特，第一个输入数变为010，计算结果为110，计算结果不变
 * <p>
 * 3、交换第2个比特和第3个比特，第一个输入数变为001，计算结果为111，计算结果改变
 * <p>
 * 故只有一种交换会改变计算结果。
 * <p>
 * 输入	6
 * <p>
 * 011011
 * <p>
 * 110110
 * <p>
 * 输出	4
 * <p>
 * 说明
 * 原本011011和110110的或结果是111111，但是第一个输入数发生如下比特交换会影响最终计算结果：
 * <p>
 * 1、交换第1个比特和第3个比特，第一个输入数变为110011，计算结果变为110111
 * <p>
 * 2、交换第1个比特和第6个比特，第一个输入数变为111010，计算结果变为111110
 * <p>
 * 3、交换第3个比特和第4个比特，第一个输入数变为010111，计算结果变为110111
 * <p>
 * 4、交换第4个比特和第6个比特，第一个输入数变为011110，计算结果变为111100
 * <p>
 * 其他交换都不会影响计算结果，故输出4.
 * <p>
 * 题目解析
 * <p>
 * 我们假设第一个输入数是bin1，第二个输入数是bin2。
 * <p>
 * 需要注意的是，本题不能去求解bin1的全排列，因为题目说，发生或运算时，bin1只有某两位会发生交换。而全排列无法保证只有两位发生交换，很可能有多位发生交换。
 * <p>
 * 另外，本题的bin1,bin2的长度都为N，1≤N≤1000000，这个数量级求解全排列肯定会超时的。
 * <p>
 * 因此，本题不推荐使用全排列解法。
 * <p>
 * 我的解题思路如下：
 * <p>
 * 二进制的或运算特点是：进行运算的两个二进制数，对应某位上数有一个为1，则结果1，否则结果为0。
 * <p>
 * 因此，我们可以忽略对bin2的值为1的位的检查，因为不管bin1对应位值变为多少，结果都为1，不会造成结果改变。
 * <p>
 * 只对bin2的值为0的位进行检查即可。
 * <p>
 * 此时有两种情况：
 * <p>
 * bin2值为0的位，在bin1对应位的值为：
 * <p>
 * 0：则正确结果为0，想要不同结果，则需要将bin1该位和bin1上值位1的位交换
 * <p>
 * 1：则正确结果为1，想要不同结果，则需要将bin1该位和bin1上值为0的位交换
 * 比如用例1中：
 * <p>
 * <p>
 * bin1 = "010"
 * <p>
 * bin2 = "110"
 * <p>
 * bin2值为0的位只有1个，就是第三位，而对应bin1的第三位的值为0，因此bin1需要将该位值变为1，才能产生不同结果，而变为1的交换策略只有一个，那就是其第二位和第三位交换。
 * <p>
 * 比如用例2中：
 * <p>
 * bin1 = "011011"
 * <p>
 * bin2 = "110110"
 * <p>
 * 即将bin1种第三位的1替换为0，有两种策略，将bin1中第六位的1替换为0，有两种策略，因此一共是2+2=4种。
 * <p>
 * 但是还有一种特殊情况，即
 * <p>
 * bin1 = "1001"
 * <p>
 * bin2 = "0001"
 * <p>
 * 就是出现重叠交换策略的情况：
 * <p>
 * bin1第一位1替换为0，有两种策略，替换后bin1分别为：0101、0011
 * <p>
 * bin1第二位0替换为1，有两种策略，替换后bin1为：0101、1100
 * <p>
 * bin1第三位0替换为1，有两种策略，替换后bin1为：0011、1010
 * <p>
 * 造成重叠的原因就是bin2值为0的位在bin1对应位上的值既有位1的，又有为0的。bin1这些位1，和位0的互相交换就会产生重叠情况。
 * <p>
 * 去重策略是：6 - 1 * 2 = 4
 * <p>
 * 6的含义是包含重复情况的所有交换策略，1*2的含义是bin1、bin2对应位组合为01的有一个，对应位组合为00有两个，因此重复策略为1*2个。
 * <p>
 * 我的解题思路如下，找出bin2值为0的位，并统计对应位上bin1的值为0的有x个，值为1的有y个，同时统计bin1总共有多少个1（假设a个），多少个0（假设b个），然后就可以用公式：
 * <p>
 * x * a + y * b - x * y
 * <p>
 * 比如用例1，x = 1，y=0，a=1，b=2，最终结果为 1 * 1 + 0 * 2 - 1 * 0 = 1
 * <p>
 * 比如用例2，x = 0,  y=2,  a= 4, b=2，最终结果为 0 * 4 + 2 * 2 - 0 * 2 = 4
 * <p>
 * 再比如自测用例：
 * <p>
 * 4
 * <p>
 * 1001
 * <p>
 * 0001
 * <p>
 * 其中 x = 2，y=1, a=2,b=2，最终结果为：2*2 + 1*2 - 2*1 = 4
 * <p>
 * 2023.06.18
 * <p>
 * 本题Java使用int可能会发生整型溢出，因此建议使用long
 */
public class WrongOrCircuit {
    public static void main(String[] args) {
        /*//处理输入
        Scanner in = new Scanner(System.in);

        int n = Integer.parseInt(in.nextLine());
        char[] input_str1 = in.nextLine().toCharArray();
        char[] input_str2 = in.nextLine().toCharArray();*/

        int n = 6;
        char[] input_str1 = "011011".toCharArray();
        char[] input_str2 = "110110".toCharArray();

        System.out.println(getResult(n, input_str1, input_str2));
    }

    public static int getResult(int n, char[] input_str1, char[] input_str2) {
        List<Integer> c = new ArrayList<Integer>();
        int[] cnt = new int[2];
        for (int i = 0; i < n; i++) {
            if (input_str2[i] == '0') {
                //System.out.println(input_str1[i]);
                c.add(Integer.parseInt(String.valueOf(input_str1[i])));
            }
            if (input_str1[i] == '0') {
                cnt[0] += 1;
            } else {
                cnt[1] += 1;
            }
        }

        int total = 0;

        for (int i = 0; i < c.size(); i++) {
            total += cnt[c.get(i) ^ 1]; // 位异或 0^1=1 1^1=0 判断是0是1
            cnt[c.get(i)] -= 1; // 因为只要变换一位就算变化，所以要求组合（c.get(i)是input1上的，你把c.get(i)整体理解为序号就能理解这段为什么-1能生成组合）
        }

        return total;
    }
}